package problems.daily;

import java.util.*;

/**
 * 1042. 不邻接植花
 * <p>https://leetcode.cn/problems/flower-planting-with-no-adjacent/</p>
 *
 * @author dubulingbo, 2023-04-15 9:35.
 */
public class DT1042 {
    public int[] gardenNoAdj_1(int n, int[][] paths) {
        List<Integer>[] g = new List[n];

        // 1. 建图
        for (int i = 0; i < n; ++i) {
            g[i] = new ArrayList<>(3);
        }

        for (int[] p : paths) {
            g[p[0] - 1].add(p[1] - 1);
            g[p[1] - 1].add(p[0] - 1);
        }

        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            // 当前点还未涂色
            if (ans[i] == 0) {
                bfs(g, i, ans);
            }
        }

        return ans;
    }

    private void bfs(List<Integer>[] g, int start, int[] colors) {
        Queue<Integer> que = new ArrayDeque<>();
        que.offer(start);

        while (!que.isEmpty()) {

            for (int i = que.size(); i > 0; --i) {
                int cur = que.poll();
                // 标记当前节点的相邻节点已使用的颜色
                boolean[] usedColors = new boolean[5];
                for (int adj : g[cur]) {
                    if (colors[adj] > 0) {
                        usedColors[colors[adj]] = true;
                    } else {
                        // 相邻、未着色的节点入队
                        que.offer(adj);
                    }
                }

                // 总是给当前节点涂上编号尽可能小的颜色
                for (int co = 1; co < 5; ++co) {
                    if (!usedColors[co]) {
                        colors[cur] = co;
                        break;
                    }
                }
            }
        }
    }

    public int[] gardenNoAdj(int n, int[][] paths) {
        List<Integer>[] g = new List[n];

        // 1. 建图
        for (int i = 0; i < n; ++i) {
            g[i] = new ArrayList<>(3);
        }

        for (int[] p : paths) {
            g[p[0] - 1].add(p[1] - 1);
            g[p[1] - 1].add(p[0] - 1);
        }

        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            // 标记当前节点的相邻节点已使用的颜色
            boolean[] usedColors = new boolean[5];
            for (int adj : g[i]) {
                usedColors[ans[adj]] = true;
            }

            // 总是给当前节点涂上编号尽可能小的颜色
            for (int c = 1; c < usedColors.length; ++c) {
                if (!usedColors[c]) {
                    ans[i] = c;
                    break;
                }
            }
        }

        return ans;
    }
}
